This invention relates to a method for configuring a finite impulse response filter in a programmable logic device, and more particularly to efficiently configuring a finite impulse response filter of arbitrary size.
Programmable logic devices are well known. Early programmable logic devices were one-time configurable. For example, configuration may have been achieved by “blowing”—i.e., opening—fusible links. Alternatively, the configuration may have been stored in a programmable read-only memory. Those devices generally provided the user with the ability to configure the devices for “sum-of-products” (or “P-TERM”) logic operations. Later, such programmable logic devices incorporating erasable programmable read-only memory (EPROM) for configuration became available, allowing the devices to be reconfigured.
Still later, programmable logic devices incorporating static random access memory (SRAM) elements for configuration became available. These devices, which also can be reconfigured, store their configuration in a nonvolatile memory such as an EPROM, from which the configuration is loaded into the SRAM elements when the device is powered up. These devices generally provide the user with the ability to configure the devices for look-up-table-type logic operations.
As programmable logic devices have become larger, it has become more common to add specialized blocks to perform particular functions that have become more common in programmable logic devices. For example, at some point, such devices began to be provided with embedded blocks of random access memory that could be configured by the user to act as random access memory, read-only memory, or logic (such as P-TERM logic); such embedded blocks might even be provided in different sizes on the same device. Other types of memory, such as read-only memory (ROM) or shift registers, also have been provided. More recently, multiplier circuits have been provided on programmable logic devices. Whereas in prior programmable logic devices space was not available for dedicated multipliers, current larger devices can accommodate multipliers. This spares users from having to create multipliers by configuring the available logic. Moreover, as described in commonly-assigned U.S. Pat. No. 6,538,470, which is hereby incorporated by reference in its entirety, specialized multiplier blocks may be provided including multipliers and other arithmetic circuits such as adders and/or subtracters and/or accumulators. Such blocks are sometimes referred to as “multiplier-accumulator blocks” or “MAC blocks.” Such blocks, for example, may be useful in digital signal processing, such as is performed in audio applications, and therefore such specialized multiplier blocks also are sometimes referred to as “DSP blocks.”
Such specialized multiplier blocks typically are capable of operations up to a certain size. For example, a specialized multiplier block may be provided that can perform a single 36-bit-by-36-bit multiplication operation, or up to four individual 18-bit-by-18-bit multiplication operations which can be combined by the aforementioned adders.
One use for such a specialized multiplier block may be as a finite impulse response (FIR) filter, or portion of a FIR filter. In a FIR filter, which is commonly used for DSP operations, samples of a signal to be processes are multiplied by a fixed set of coefficients and those products are added together. A FIR filter may be characterized by its number of taps, which corresponds to the number of multipliers and also to the number of coefficients.
A specialized multiplier block of the type described above necessarily has a finite number of multipliers. While such a block is particularly well-adapted to be configured as a FIR filter, if the number of multipliers required (i.e., the number of taps) exceeds the number of multipliers in the block, then more than one block must be used to create the required filter. For example, specialized multiplier blocks in the STRATIX® family of PLDs available from Altera Corporation, of San Jose, Calif., specialized multiplier blocks typically have four multipliers. On the other hand, in many DSP applications, FIR filters with over 200 taps are not unheard of. Thus, implementation of a FIR filter is frequently spread over a large number of specialized multiplier blocks, giving rise to routing and speed issues.
It would be desirable to be able to configure a FIR filter in a programmable logic device as efficiently as possible for a given number of filter taps.